﻿using System;
using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 两个数组的交集II
    {
        /// <summary>
        /// https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2y0c2/
        /// </summary>
        public class Solution
        {
            /// <summary>
            /// 执行用时：264 ms, 在所有 C# 提交中击败了98.15%的用户
            /// 内存消耗：31.1 MB, 在所有 C# 提交中击败了25.62%的用户
            /// </summary>
            /// <param name="nums1"></param>
            /// <param name="nums2"></param>
            /// <returns></returns>
            public int[] Intersect(int[] nums1, int[] nums2)
            {
                Dictionary<int, int> dicts = new Dictionary<int, int>();
                Dictionary<int, int> dicts2 = new Dictionary<int, int>();

                foreach (var item in nums1)
                {
                    if (dicts.ContainsKey(item)) dicts[item]++;
                    else dicts.Add(item, 1);
                }
                foreach (var item in nums2)
                {
                    if (dicts2.ContainsKey(item)) dicts2[item]++;
                    else dicts2.Add(item, 1);
                }

                List<int> result = new List<int>();

                foreach (var item in dicts)
                {
                    if (dicts2.ContainsKey(item.Key))
                    {
                        var min = Math.Min(dicts2[item.Key], item.Value);
                        for (var i = 0; i < min; i++) result.Add(item.Key);
                    }
                }
                return result.ToArray();
            }
        }
        ITestOutputHelper output;

        public 两个数组的交集II(ITestOutputHelper output)
        {
            this.output = output;
        }

        [Fact]
        public void Test1()
        {

            Solution S = new Solution();
            int[] r;

            r = S.Intersect(new int[] { 1, 2, 2, 1 }, new int[] { 2, 2 });
            foreach (var item in r)
            {
                output.WriteLine("" + item);
            }
            output.WriteLine("");
            r = S.Intersect(new int[] { 4, 9, 5 }, new int[] { 9, 4, 9, 8, 4 });
            foreach (var item in r)
            {
                output.WriteLine("" + item);
            }
            output.WriteLine("");
        }
    }
}
